iT邦幫忙

2021 iThome 鐵人賽

DAY 3
1

編譯器做了什麼?

我們知道使用機器指令撰寫程式碼是非常麻煩的事情,也會使開發程式的效率不高,編譯器就是將來源碼(source code)翻譯成機器語言(object code)的一種工具。

Source Code 到 Object Code 中間發生了什麼事情

Complier 會分三個階段

1.Front-end: 將程式碼切成一個一個的字,然後照該語言的邏輯變成一個抽象語法樹(AST)
2.Middle-end: 將AST轉換成中間語言(IR),並優化這個IR
3.Back-end:將IR 轉換成目標碼並且優化

詞彙分析(Lexical analysis)

首先將 來源碼 (Source Code) 輸入到 掃描器(Scanner),掃描器只是簡單地進行語法分析,使用一種類似於有限狀態機(Finite State Machine) 的算法將 Source Code 的字符序列分割成一系列的 Token。

unsigned background(unsigned foreground) {
    if ((foreground >> 16) > 0x80) {
        return 0;
    } else {
        return 0xffffff;
    }
}

有一個叫做lex 的程序可以實現詞法掃描,他會按照描述好的詞彙規則將輸入字符分割成一個個的Token,編譯器的開法者就無需對每個編譯器開發一個獨立的掃描器,而是根據需要改變語法規則就可以了

語法分析 (Parser)

Parser 讀取 token,然後對照語法規則來判斷 token 屬於哪個語法的哪個部分,遇到不合法的 token 就會丟出 Parse error,最後產生語法樹(Synta Tree)

那麼語法規則該怎麼表示呢?
是一種用來表示上下文無關文法的語言,原理非常複雜,因此不贅述,定義了語法之後,我們就可以拿這個文法來實作真的parser 程式碼,Parser 使用 LL 或 LR 兩種方式轉換語法樹,而通常在現代 parser generator 的技術都很成熟了,只要把 CFG 定義好丟給 parser generator 就可以產生 parser 了。

語意分析 (Semantic analysis)

語意分析是根據語言規則和上下文,檢查 parse tree 裡的語意是否有問題。

var a:bool = 1 + ture

假設一個數字跟一個布林值相加,很明顯是錯誤的,Semantic analysis 要做的就是把這個問題抽出來,可能不只這些語意上錯誤,不同語言也可能有不同的規則,而編譯器所能分析的語意是靜態語意,所謂的靜態語意是指在編譯期間可以確定的語意,與之對應的動態語意就是只有在運行期間才可以確定的語意。

中間語言 (Intermediate code)

編譯器可能有中間語言,稱作中間表達式 Intermedia Representation(簡稱 IR),以便進行後續的優化以及對應多機器平台的機器碼。

為什麼需要先轉為 IR 優化後才轉為 Object Code?

1.如果沒有 IR,直接從 Front-end 編譯到各個機器平台的話,因為對應平台的機器目的碼都不同,這樣會有太多種的組合,以實作來說就是一個悲劇。而 IR 通常都是不相依於機器的,因此這樣更易於重用,提高開發彈性。
2.直接在語法樹上做優化較其困難,所以將 Source Code 優化器往往講整個語法樹轉換成 IR ,它是語法樹的順序表示。

程式碼生成(Code Generation)

程式碼生成器將IR轉換成機器碼,這個過程十分依賴於目標機器,因為不同機器有著不同的CPU架構而有不同的指令集,另外也有一種虛擬機 (VM, Virtual Machine),主要是建立跨平台的執行環境,讓相同的目標碼在任何機器上執行,像是 JVM 它的目標碼就是 bytecode 。
最後目標碼優化器對上述機器碼進行優化,這邊屬於跟機器平台有關的優化,往往利用硬體平台的特性來幫助優化,IR的優化屬於與機器無關的優化。

參考資料

实现一个编译器需要实现哪些流程?
人人都能读懂的编译器原理
一點都不深入的了解 Compiler、 Interpreter 和 VM


上一篇
Day2.程式運行的基本概念(預處理、編譯、組譯、鏈結)
下一篇
Day.4深入理解連結之Object file
系列文
30天從0開始探索嵌入式世界15
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言